//1.暴力双循环，时间复杂度太高了

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int count=0;
     
        for(int i=0;i<nums.size();++i) {
            int sum=0;
            for(int j=i;j<nums.size();++j){
                sum+=nums[j];
                if(sum==k)  count++;
                
            }
        }
        return count;
    }
};
//2.哈希表＋前缀和
/*
子数组和与前缀和关系
任意连续子数组 nums[j..i]（j<=i）的和：
subarraySum(𝑗,𝑖)=𝑠𝑢𝑚[𝑖]−𝑠𝑢𝑚[𝑗−1]要让它等于 k，需满足：𝑠𝑢𝑚[𝑖]−𝑠𝑢𝑚[𝑗−1]=𝑘⟹𝑠𝑢𝑚[𝑗−1]=𝑠𝑢𝑚[𝑖]−𝑘
换句话说，每当我们在索引 i 处得到 𝑠𝑢𝑚[𝑖]，只要之前有出现过 𝑠𝑢𝑚[𝑖] - k，就有对应的子数组和为 k。(即i位置之前的前缀和有𝑠𝑢𝑚[𝑖]−𝑘出现)

前缀和公式是sum[i]=sum[i-1]+num[i];
当i=0，sum[0]=sum[-1]+num[0]; 我们默认sum[-1]=0，因为num[-1]不存在，我们索引0前面的前缀和就等于0，毕竟什么都没有-------》对应 hashmap[0]=1;
*/
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> hashmap;
        hashmap[0]=1;
        int sum=0;
        int ret_count=0;
        for(auto&e : nums) {
            sum+=e;
            if(hashmap.count(sum-k)) {
                ret_count+= hashmap[sum-k]; //统计当前多少个前缀和𝑠𝑢𝑚[𝑗−1]满足条件，然后加上
            }
            hashmap[sum]++; //哈希表记录前缀和次数
        }

        return ret_count;

    }
};